package com.lun.medium;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.lun.util.BinaryTree.TreeNode;

public class FindLargestValueInEachTreeRow {

	//方法一：BFS
	public List<Integer> largestValues(TreeNode root) {
    	List<Integer> result = new ArrayList<>();
    	if(root == null) return result;
    	Queue<TreeNode> queue = new LinkedList<>();
    	queue.offer(root);
    	
    	
    	while(!queue.isEmpty()) {
    		int max = Integer.MIN_VALUE; 	
    		for(int size = queue.size(); size > 0; --size ) {
    			TreeNode node = queue.poll();
    			
    			if(node.val > max)
    				max = node.val;
    			
    			if(node.left != null)
    				queue.offer(node.left);
    			
    			if(node.right != null)
    				queue.offer(node.right);
    			
    		}
    		result.add(max);
    	}
    	
    	return result;
    }
    
    //方法二：DFS
    public List<Integer> largestValues2(TreeNode root) {
    	List<Integer> result = new ArrayList<>();
    	largestValues2(root, result, 0);
    	return result;
    }
    
    private void largestValues2(TreeNode node, List<Integer> result, int level) {
    	if(node == null) return;
    	
    	if(level >= result.size()) {
    		result.add(node.val);
    	}else {
    		if(result.get(level) < node.val)
    			result.set(level, node.val);
    	}
    	
    	largestValues2(node.left, result, level + 1);
    	largestValues2(node.right, result, level + 1);
    }
    
}
